1. Technical Field
The present invention relates in general to an improved method and system for managing communications networks. In particular, the present invention relates to a method and system within a telecommunications network for efficiently adapting a pause interval flow control mechanism to a rate-based flow control mechanism. More particularly, the present invention relates to a method and system for allocating bandwidth among a plurality of sessions that utilize both pause interval and rate-based flow control.
2. Description of the Related Art
Traditional Ethernet utilizes the carrier sense multiple access with collision detection (CSMA/CD) network protocol to insure that there is no more than a single station transmitting on a segment at any instant. This contention resolution algorithm has inherent flow control capability. Therefore, in a traditional Ethernet network, congestion can typically happen only at bridges. Conventionally, slow network speeds and flow control provided by higher layer protocols such as Transmission Control Protocol/Internet Protocol (TCP/IP) have meant that flow control at switches was not an issue. However, the recent increase in network speeds up to gigabits per second, coupled with full-duplex transmission capabilities, has mandated the need for a flow control mechanism. The goals of such flow control include efficiency and fairness. To this end, The IEEE 802.3 working group has standardized a mechanism for asymmetric flow control for full duplex Ethernet LANs. The draft standard IEEE 802.3x defines a hop flow control method wherein a switch experiencing congestion delivers a frame to its upstream switch forcing the upstream switch to pause all transmission from a designated port for a time period specified in the frame. The draft standard IEEE 802.3x, requires mandatory interpretation of the mechanisms defined therein for Gigabit Ethernet (1000 Mbs) and 100 Mbs Ethernet while being optional for slower networks with 10 Mbs links.
The standard IEEE 802.3x specifies a pause operation as follows. The purpose of a pause operation is to inhibit transmission of data frames from another station for a period of time. A Media Access Control (MAC) station which wants to inhibit transmission from another station generates a 64-byte pause control frame containing several information fields. One such field is a 6-byte (48-bit) MAC address of the station requesting the pause. Another is a globally assigned 48-bit multicast address assigned by the IEEE for the flow control function. Other fields include a type/length field indicating that the frame is a control frame, a PAUSE opcode field, a pause interval (length of time of the requested pause) field, and a PAD field.
The timespan of a pause interval is measured and assigned in units of time slots. Currently, a time slot is defined as the amount of time required to transmit a 64 byte packet on the given medium. For example, the time slot for 10 Mbs Ethernet is 51.2 microseconds.
A bridge which conforms to IEEE 802.1D standard (ISO/IEC Final CD 15802-3 Information technologyxe2x80x94Telecommunications and information exchange between systemsxe2x80x94Local and metropolitan area networksxe2x80x94Common specificationsxe2x80x94part 3: Media Access Control (MAC) bridges, IEEE P802.1D/D15) will recognize frames with the well-known multicast address and it will not forward such frames.
When a station receives a MAC control frame having a destination address equal to the reserved multicast address, or with the destination address equal to the station""s own unique MAC address, and with the PAUSE opcode, the compliant station is required to start a timer for the value indicated by the pause time field in the frame. The new pause time will overwrite any pause value that may be in progress, whether shorter or longer. Note that although the receiving station is required to process and not forward any such frame that includes either the reserved multicast address or its own address, generating a pause frame with any destination address other than the reserved multicast address violates the current standard. Having a station react to both addresses was done to allow future expansion of the flow control protocol to support half duplex links or end-to-end flow control.
The notion of fairness in allocation of network resources is very difficult to quantify and may be defined in a number of ways. One of the simplest definitions of fair allocation is that which provides equal distribution of network resources among all sessions. Every network link has a capacity. Every session has a source node, a destination node, a single path connecting the source node to the destination node, and an offered send rate. Simply put, the goal of max-min fairness is to arrive at send rates for all sessions so that no send rate can be increased without causing some other send rate to decrease due to resulting congestion in some link.
Consider, for instance, the scenario depicted in FIG. 1. As illustrated in FIG. 1, the bottleneck link for sessions 110, 112, and 114 is link 116. Since link 116 has a capacity of 1, each of sessions 110, 112, and 114 is expected to be provided a rate of ⅓. The second link 118 also has a capacity of 1 and is shared by sessions 114 and 122. Since session 114 has already been limited to a flow rate of ⅓, session 122 may be allocated a rate of ⅔. Finally, the capacity of the third link 120 is 2 units of bandwidth. Therefore link 120 will have 1 unit of unutilized bandwidth due to the upstream bottlenecks of sessions 114 and 122.
The example in FIG. 1 illustrates the concept of max-min fairness in which the goal is to maximize the minimum capacity allocated to any session. For a formal treatment of max-min fairness and for an algebraic algorithm for computing the max-min fair share, reference is may be made to D. Bertsekas and R. Gallager, Data Networks, Prentice-Hall, Englewood Cliffs, N.J., 1992, incorporated herein by reference. The algebraic algorithm explained therein requires global, simultaneous knowledge of all session demands and all link capacities.
A problematic consequence of max-min fairness appears in FIG. 2. The configuration illustrated in FIG. 2 is adapted from M. Molle and G. Watson, 100BaseT/IEEE 802.12/Packet Switching, IEEE Communications Magazine, August 1996. Here a switch, SW2204, experiences congestion on its output port into a link 210 of capacity 2. The response of SW2204 is to require traffic in both input links, 206 and 212, which feed link 210 to reduce flows to 1. Thus both Session0218 and Session1220 are required to reduce rates to 1, as well as Session2222. It should be noted, however, that optimal max-min allocation would allow rates of 1 for Session0218 and Session2222, but 9 for Session1220.
Asynchronous Transfer Mode (ATM) is a rapidly developing network technology capable of providing real-time transmission of data, video, voice traffic. ATM is connection-oriented and utilizes cell-switching technology that offers high speed and low latency for the support of data, voice, and video traffic. ATM provides for the automatic and guaranteed assignment of bandwidth to meet the specific needs of applications, making it ideally suited for supporting multimedia as well as for interconnecting local area networks (LANs).
ATM serves a broad range of applications very efficiently by allowing an appropriate Quality of Service (QoS) to be specified for differing applications. Various service categories have been developed to help characterize network traffic including: Constant Bit Rate (CBR), Variable Bit Rate (VBR), Unspecified Bit Rate (UBR), and Available Bit Rate (ABR).
Standardized mechanisms for rate-based flow control have been developed for the ABR class of service. ABR is a best effort service class for non-real-time applications such as file transfer and e-mail. An amount of bandwidth termed minimum cell rate (MCR) is reserved for each session. Each session then gets an additional amount of traffic depending upon availability. The total amount of bandwidth that a session is allowed to utilize at any instant is given by the allowable cell rate (ACR). A session is guaranteed a very low loss provided its traffic conforms to its ACR. There are, however, no delay guarantees. An elaborate flow control mechanism is utilized to maximize network utilization, minimize loss, and ensure that sessions share the bandwidth fairly. The flow control mechanism ABR data transmission makes use of available bandwidth and protects against data loss through a congestion notification feedback method. In order to perform flow control, the source of an ABR session periodically sends out control cells called resource management (RM) cells. Switches along the path may indicate congestion by modifying fields in the RM cell. The destination is responsible for turning around the RM cells and sending them back to the source, which then adjusts its ACR based upon that feedback.
Some of the fields in the RM cell which are relevant to implementation of ABR flow control are as follows.
CCR: the current cell rate of the session. This field is filled in by the source with the ACR and is not modified by any of the network elements along the path or the destination.
CI: a single bit utilized as a congestion indicator. In relative rate (RR) marking switches, a congested switch will set this bit in the RM cell. In the case of explicit forward congestion indication (EFCI) switches, the switch sets the EFCI bit in the header of data cells. The destination is then responsible for saving the congestion status and appropriately setting the CI bit in the RM cell before sending it back to the source. A source which receives an RM cell with the CI bit set will reduce its ACR by a predetermined fraction of what it currently holds. This field is important for EFCI and RR marking switches only.
NI: a single bit utilized as a xe2x80x9cno-increasexe2x80x9d indicator. In RR marking switches, a switch operating at its desired utilization will set this bit in the RM cell. A source which receives an RM cell with its NI bit set will simply maintain its current value of ACR, provided that the CI bit is zero.
ER: this field is utilized only by explicit rate switches. The switch fills this field with the computed estimate of the ACR for the session.
The CI and NI fields are interesting to the source if any of the switches along its path are either RR or EFCI marking switches. If neither of these bits is set, the source increases its send rate by a predetermined fixed quantity. Base on the feedback received from the returning RM cells, the source maintains the ACR value or less for the session. If the session is to be considered conforming, its sending rate must never exceed its ACR. The ACR is computed by the source in the case of EFCI and RR marking switches. For explicit rate (ER) switches, the ACR is simply set to the value contained in the ER field of the returning RM cells.
Switches which support ABR fall into one of three categories based upon their ability to recognize and process RM cells and the per-session state information therein.
Explicit forward congestion indication (EFCI) is the most basic form of ABR flow control. In this scheme, the switches need not be modified at all. Only the source and destination need modification. The switch does not even recognize RM cells. If the switch is congested, it sets a combination of bits in the header of the data cells to indicate congestion. The destination must save this congestion information. When the next RM cell arrives at the destination, the destination will set the CI bit in the RM cell.
Relative rate (RR) marking switches must be able to recognize RM cells. The switch then has the option of setting the NI bit, the CI bit, or neither. If the switch can handle more traffic, it sets neither and increases its rate. If the switch is operating at capacity, perhaps indicated by queue lengths, it will set the NI bit only. When a source receives an RM cell with NI bit set but CI bit not set, it will maintain its current ACR value. If the switch is congested, it will set the CI bit. A source receiving an RM cell with CI bit set will reduce its ACR.
Explicit rate (ER) algorithms assign the computation effort of send rates to the switches. Each switch along a path of a session computes an estimate of the ACR for the session. The minimum of the explicit rate indicated by all switches along the path is returned t the source in the RM cell. The source simply sets its allowable rate to-the value indicated in the RM cell. ER switches are significantly more complex to implement because of the computations that must be performed and the per-session state information that must be maintained by the switch. Further, for the scheme to-be effective, the switch must be able to make accurate utilization measurements in order to estimate the capacity available for ABR traffic. All of the requirements make it difficult to build a competitively priced ER switch for operation in high speed networks.
Due to its inherent speed and switching efficiency characteristics, ATM is increasingly being utilized as a backbone network for connecting packet-switching LANs. As utilized herein, xe2x80x9cheterogeneous networksxe2x80x9d refer to telecommunications networks that combine packet-switching subnetworks with a cell-switching network (Ethernet connected to an ATM backbone, for example). Similarly, a xe2x80x9chybrid sessionxe2x80x9d refers to a telecommunications session conducted over both a packet-switched and a cell-switched network. It is clearly desirable for the subnetworks within a heterogeneous network to be operably compatible. Variable data packet size is a characteristic of packet-switched systems such as Ethernet. Cell-switched networks, such as ATM, utilize a fixed size data packet known as a xe2x80x9ccellxe2x80x9d. An ATM cell is typically 53 bytes, five of which are utilized for virtual routing information and the other 48 of which are utilized for data.
The ATM Forum LAN Emulation (LANE) working group has developed a specification for seamless interworking between IEEE 802 style LAN technologies and ATM. For small networks, protocol conversion overhead between LANs and an ATM backbone at a router is acceptable. However, for larger systems with Ethernet legacy LANs, a more efficient solution is LAN emulation (LANE). A LANE system consists of some combination of end systems on legacy LANs and end systems attached directly to an ATM switch. LANE allows network managers to integrate ATM into their existing LAN infrastructure in a way that is transparent to end systems, thereby allowing for faster deployment of ATM in campus backbone networks.
Thus LANE must define the following:
1. How end systems on two separate LANs in the same Media Access Control (MAC) layer can exchange MAC frames across the ATM network.
2. How end system LANs attached directly to an ATM switch can interoperate.
End systems attached to a legacy LAN are not affected by LANE. Such end systems utilize the ordinary protocols. However, at the point of connection to the ATM backbone, an ATM-to-LAN converter is utilized. The process of converting LAN frames to cells and cells to LAN frames is performed by the ATM Adaptation Layer (AAL). LANE instructions are utilized to coordinate and map LAN frames across an ATM link.
As previously explained, fast Ethernet utilizes intermittent pause intervals as a means to control traffic flow and avoid excessive network congestion. ATM, on the other hand, utilizes feedback from RM cells to implement a rate-based flow control in terms of altering a rate of transmission measure in bits per second. In order to enhance the practicability and quality of Ethernet-to-ATM backbone networks, an method and system for mapping a pause interval flow control to rate-based flow control would be useful.
In view of the above can therefore be appreciated that a need exists for a method and system within a heterogeneous telecommunications network for adapting pause interval flow control mechanisms to rate-based flow control mechanisms. If implemented, such a method and system would ensure optimum allocation of limited bandwidth among a plurality of hybrid sessions.
It is therefore an object of the invention to provide an improved method and system for managing communications networks.
It is another object of the invention to provide a method and system within a telecommunications network for efficiently adapting a pause interval flow control mechanism to a rate-based flow control mechanism.
It is a further object of the invention to allocate bandwidth among a plurality of sessions that utilize both pause interval and rate-based flow control.
The above and other objects are achieved as is now described. A method and system within a telecommunications network for allocating available bandwidth among a plurality of sessions that share a common data link are disclosed. First, a repeating unit time interval is designated for conducting the plurality of sessions. Next, the input flow rate from the source node of each of the sessions into the common data link is monitored. Thereafter, a target flow rate is computed and assigned to each of the sessions. The sum of the target flow rates is equal to the available bandwidth of the common data link. Finally, for each of the sessions in which the monitored input flow rate exceeds the assigned target flow rate, the source node is dynamically paused during each repeating unit time interval, such that the monitored input flow rate conforms to the assigned target flow rate for each of the sessions.